package leetcode.jianzhioffer;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2021-11-15 12:45
 **/
public class JianZhiOffer59II {

    Deque<Integer> deque;
    Deque<Integer> deque2;

    public JianZhiOffer59II() {
        deque = new LinkedList<>();
        deque2 = new LinkedList<>();
    }

    public int max_value() {
        return deque2.isEmpty() ? -1 : deque2.peek();
    }

    public void push_back(int value) {
        while (!deque2.isEmpty() && deque2.peekLast() < value) {
            deque2.pollLast();
        }
        deque.offer(value);
        deque2.offer(value);
    }

    public int pop_front() {
        if (deque.isEmpty()) {
            return -1;
        }
        int a = deque.poll();
        if (a == deque2.peekFirst()) {
            deque2.poll();
        }
        return a;
    }

}
